//Given a string s, return the longest palindromic substring in s. 
//
// 
// Example 1: 
//
// 
//Input: s = "babad"
//Output: "bab"
//Note: "aba" is also a valid answer.
// 
//
// Example 2: 
//
// 
//Input: s = "cbbd"
//Output: "bb"
// 
//
// Example 3: 
//
// 
//Input: s = "a"
//Output: "a"
// 
//
// Example 4: 
//
// 
//Input: s = "ac"
//Output: "a"
// 
//
// 
// Constraints: 
//
// 
// 1 <= s.length <= 1000 
// s consist of only digits and English letters. 
// 
// Related Topics String Dynamic Programming 👍 14354 👎 842


package leetcode.editor.en;

public class _5_LongestPalindromicSubstring {
    public static void main(String[] args) {
        Solution solution = new _5_LongestPalindromicSubstring().new Solution();
        String ababab = solution.longestPalindrome1("babad");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String longestPalindrome1(String s) {
            int l = s.length()*2-1;
            String cur = "";
            for (int i = 0; i < l; i++) {
                int left = i/2;
                int right = left+i%2;
                while (left>=0&&right<s.length()&&s.charAt(left)== s.charAt(right)){
                    if (cur.length()<(right-left+1)){
                        cur = s.substring(left, right+1);
                    }
                    left--;
                    right++;
                }
            }
            return cur;
        }


        public String longestPalindrome(String s) {
            int length = s.length()*2-1;
            String r = "";
            for (int i = 0; i < length; i++) {
                int left = i/2;
                int right = left + i%2;
                while (left>=0 &&right<s.length()&& s.charAt(left)==s.charAt(right)){
                    if (r.length()<(right-left+1)) {
                        r = s.substring(left, right+1);
                    }
                    left--;
                    right++;
                }
            }
            return r;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}